/*
 * @lc app=leetcode.cn id=1631 lang=typescript
 *
 * [1631] 最小体力消耗路径
 */

// @lc code=start
//  思路：最短路径
//  参考：https://labuladong.github.io/algo/2/17/34/

function minimumEffortPath(heights: number[][]): number {
    // 返回所有相邻节点的坐标
    const adj = (matrix: number[][], x: number, y: number): number[][] => {
        const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        const m = matrix.length, n = matrix[0].length
        const neighbors: number[][] = []
        for (const dir of dirs) {
            const nx = x + dir[0], ny = y + dir[1]
            if (nx >= m || nx < 0 || ny >= n || ny < 0) {
                continue
            }
            neighbors.push([nx, ny])
        }
        return neighbors
    }
    const m = heights.length, n = heights[0].length
    // 初始化dp
    const effortTo: number[][] = Array.from(new Array(m), () => new Array(n).fill(Infinity))
    // base case
    effortTo[0][0] = 0
    // 存储队列，从(0, 0)开始
    const queue = [[0, 0, 0]]

    while (queue.length) {
        const curr = queue.shift()
        const currX = curr![0], currY = curr![1], currEffort = curr![2]
        // 到达终点
        if (currX === m - 1 && currY === n - 1) {
            return currEffort
        }
        if (currEffort > effortTo[currX][currY]) {
            continue
        }
        // 遍历相邻节点
        for (const neighbor of adj(heights, currX, currY)) {
            const nextX = neighbor[0], nextY = neighbor[1]
            // 计算从 (curX, curY) 达到 (nextX, nextY) 的消耗
            const effortToNext = Math.max(effortTo[currX][currY], Math.abs(heights[currX][currY] - heights[nextX][nextY]))
            if (effortTo[nextX][nextY] > effortToNext) {
                effortTo[nextX][nextY] = effortToNext
                queue.push([nextX, nextY, effortToNext])
                // 保证小的在前
                queue.sort((a, b) => a[2] - b[2])
            }
        }
    }
    return -1
};
// @lc code=end

console.log(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]]))
console.log(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]]))
console.log(minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]]))
